package com.mamingchao.basic.dichiotomy;

/**
 * 一个有序数组，查找最 >=指定值最左侧
 * Created by mamingchao on 2020/11/14.
 */
public class LeftestOfGreaterOrEq {

    private static int findLeftestOfGreaterOrEq(int[] arr, int value){
        int leftIndex = 0;
        int rightIndex = arr.length-1;
        int index = -1;

        while (rightIndex >= leftIndex) {
            int middleIndex  = leftIndex + ((rightIndex - leftIndex)>>1);
            if (arr[middleIndex] >= value) { // looking up left side
                index = middleIndex;
                rightIndex = middleIndex -1;
            } else {
                leftIndex = middleIndex + 1; // looking up right side
            }
        }

        return index;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {1,1,1,1,2,2,3,3,3,4,5,5};

        System.out.println(findLeftestOfGreaterOrEq(arr,2));
    }

}
